package com.example.demo.tixiban;

import java.util.HashMap;

/**
 * @author xujm
 * @version V2.4
 *
 *  对于一个字符串 abc,
 *
 * 前缀树展示:
 *    p表示经过的字符串数量，e标识结尾的字符串数量
 *     p=1,  p=1  p=1  p=1
 *     e=0   e=0  e=0  e=1
 *        a    b    c
 *     x -> x  -> x ->x
 *
 */
public class 前缀树 {


    static class Node{

        int pass;
        int end;
        HashMap<Character,Node> next; // 下标应该是具体字符

        public Node(int pass, int end) {
            this.pass = pass;
            this.end = end;
            this.next = new HashMap<>(32);
        }
    }


    static class Trie{
        private Node root;

        public Trie() {
            this.root = new Node(0,0);
        }

        public void add(String word){
            if(word == null){
                return;
            }
            root.pass++;
            char[] chars = word.toCharArray();
            Node node = root;
            for(int i =0;i<chars.length;i++){
                char temp = chars[i];
                if(!node.next.containsKey(temp)){
                    node.next.put(temp,new Node(1,0));
                }else{
                    Node node1 = node.next.get(temp);
                    node1.pass++;
                }
                node = node.next.get(temp);
                if(i == chars.length-1){
                    node.end++;
                }
            }
        }

        public void remove(String word){
            if(!search(word) || word == null){
                return;
            }
            root.pass--;
            char[] chars = word.toCharArray();
            Node node = root;
            for(int i =0;i<chars.length;i++) {
                char temp = chars[i];
                if(--node.next.get(temp).pass ==0){
                    node.next.remove(temp);
                    return;
                }else{
                    node = node.next.get(temp);
                }
                if(i == chars.length-1){
                    node.end--;
                }
            }
        }

        public int preSearch(String word){
            char[] chars = word.toCharArray();
            Node node = root;
            for(int i =0;i<chars.length;i++) {
                char temp = chars[i];
                if(node.next.get(temp) == null){
                    return 0;
                }
                node = node.next.get(temp);
            }
            return node.pass;
        }

        public boolean search(String word){
            if(word == null){
                return false;
            }
            char[] chars = word.toCharArray();
            Node node = root;
            for(int i =0;i<chars.length;i++) {
                char temp = chars[i];
                if(node.next.get(temp) == null){
                    return false;
                }
                node = node.next.get(temp);
            }
            return true;
        }


    }

    public static void main(String[] args) {

        Trie trie = new Trie();
        trie.add("abcd");
        trie.add("abcde");
        trie.add("abcf");
        trie.add("cbX");
        System.out.println(trie.search("cbX"));
        System.out.println(trie.preSearch("ab"));

        trie.remove("abcde");
        System.out.println(trie.preSearch("ab"));

    }





}
